package 二叉树的最近公共祖先;

import javax.swing.tree.TreeNode;
import java.util.Deque;
import java.util.LinkedList;

public class Solution {
    public boolean getPath(TreeNode root, TreeNode node,
                           Deque<TreeNode> stack) {
        if (root == null || node == null) return false;
        stack.push(root);
        //放完之后 要检查
        if (root == node) return true;
        boolean ret1 = getPath(root.left, node, stack);
        if (ret1) return true;
        boolean ret2 = getPath(root.right, node, stack);
        if (ret2) return true;
        stack.pop();
        return false;
    }

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        //1、两个栈当中 存储好数据
        Deque<TreeNode> stack1 = new LinkedList<>();
        getPath(root, p, stack1);
        Deque<TreeNode> stack2 = new LinkedList<>();
        getPath(root, q, stack2);
        //2、判断栈的大小
        int size = Math.max(stack1.size(), stack2.size());
        if (size == stack1.size()) {
            size = stack1.size() - stack2.size();
            for (int i = 0; i < size; i++) {
                stack1.pop();
            }
        } else if (size == stack2.size()) {
            size = stack2.size() - stack1.size();
            for (int i = 0; i < size; i++) {
                stack2.pop();
            }
        }
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            TreeNode cur1 = null;
            TreeNode cur2 = null;
            cur1 = stack1.pop();
            cur2 = stack2.pop();
            if (cur1 == cur2) {
                return cur1;
            }
        }
        return null;
    }
}
